#include <bits/stdc++.h>

using namespace std;

// 普通二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
// 有关LCA问题的介绍：https://oi-wiki.org/graph/lca/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution 
{
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        // 遇到空，或者p，或者q，直接返回
        if(root == nullptr || root == p || root == q) return root;

        auto inLeft = lowestCommonAncestor(root->left, p, q);
        auto inRight = lowestCommonAncestor(root->right, p, q);
        // 左树也搜到，右树也搜到，返回root
        if(inLeft && inRight) return root;
        // inLeft和inRight一个为空，一个不为空
		// 返回不空的那个，两个都为空，返回空
        return inLeft ? inLeft : inRight;
    }
};